Error diffusion methods, such as the method described in R. W. Floyd & L. Steinberg, “An Adaptive Algorithm for Spatial Grayscale,” in the Proceedings of the Society for Information Display, vol. 17, pp 75-77 (1976) (the “Floyd-Steinberg method”), are often used to convert grayscale images to binary images on a binary output device. Such error diffusion methods typically examine a pixel in an input image, determine whether the intensity for the pixel in the input image exceeds a threshold, and assign either a light or dark binary value to the pixel in an output image based on whether it exceeds the threshold. The difference between the input image pixel intensity and the corresponding pixel intensity in the output image is the error for the pixel. Error diffusion methods assign at least a portion of the error to one or more neighboring pixels that have not been previously assigned a pixel intensity for the output image. In this manner, the total pixel intensity is substantially maintained throughout the output image without a substantial loss of resolution. However, individual pixels might be lighter or darker in the resulting image than in the input image.
For example, FIG. 1A depicts grayscale values for neighboring pixels in an input image. Each pixel has a grayscale value within a range. In a computer embodiment having 8-bit color, a low value for the range is “0” and a high value for the range is “255.”
FIG. 1B depicts the resulting light/dark values for the four pixels based on a traditional error diffusion method. In FIG. 1B, the threshold for the light/dark determination is the midpoint of the range (i.e., a grayscale value of 127.5). Since the first pixel has a grayscale value greater than the threshold, the pixel is assigned a value of “1” (e.g., “light” or “white”). The difference between the original grayscale value for the first pixel and the resulting high value is defined to be the error value, E1. In other words, the error is equal to the amount of compensation added to a pixel in order to force it to a “0” or “1” value.
For the second pixel, the error value E1 is subtracted from the original value for the pixel. Since the resulting value is less than the threshold, the second pixel is assigned a value of “0” (e.g., “dark”). The error value, E2, is computed for the second pixel. The process iterates over each subsequent pixel until all pixels are computed. Alternate error diffusion methods might diffuse the calculated error among a plurality of unconverted pixels. For example, a first portion of the error value E1 for the first pixel could be subtracted from the second pixel and a second portion could be subtracted from the third pixel.
Exemplary methods of using error diffusion to generate an output image include the methods described in U.S. Pat. Nos. 5,226,094 and 5,374,997 to Eschbach, the disclosures of which are each incorporated herein by reference in their entireties.
One problem inherent in the Floyd-Steinberg method is that displeasing textures (i.e., worms) are produced in the highlight and shadow regions. An exemplary error diffusion rendered binary output having worm effects is shown in FIG. 2.
Accordingly, modifications to the Floyd-Steinberg method, such as the one described in U.S. Pat. No. 5,353,127 to Shiau et al., which is incorporated herein by reference in its entirety, and shown in FIG. 3, have been developed to reduce this effect. The error diffusion weights (the “Shiau-Fan” or “anti-worm” coefficients) shown in FIG. 3 may be generated using simple bit-shifting techniques. As such, this error diffusion method allows for very fast calculations with limited circuitry.
A third error diffusion method, called “threshold stamping” and described in U.S. Pat. No. 5,535,019 to Eschbach, which is incorporated herein by reference in its entirety, modulates the error diffusion threshold level in order to adjust the dot placement in the extreme highlight and shadow regions. As such, the worm artifact is virtually eliminated. The stamping function requires a complete line-buffer of memory to store and adjust the slow-scan threshold video that is used to render the downstream pixels via error diffusion processing.
FIG. 4 depicts a block diagram of the main components of a traditional error diffusion color image-processing module with threshold stamping. Each error diffusion block 405a-d performs the threshold stamping and error diffusion algorithms for a particular color, such as cyan, magenta, yellow and black.
The error diffusion blocks 405a-d receive pixel information 410a-d corresponding to the color for each pixel on a scanline. The pixel information 410a-d is within a range, such as from 0 to 255, and represents the intensity of the particular color for the pixel in an input image.
The error diffusion blocks 405a-d also receive error information from the error scanline buffer memory 415a-d corresponding to the same color. Each error value is within a range, such as from −128 to 127, and represents the amount of error passed to the pixel from preceding pixels according to an error diffusion algorithm.
Moreover, the error diffusion blocks 405a-d receive threshold information from the threshold scanline buffer memory 420a-d corresponding to the same color. Each threshold value is within a range, such as from −128 to 127, and represents the change from the base threshold for the particular pixel.
The error diffusion blocks 405a-d determine whether the sum of the pixel value and the error value for a pixel is greater than the sum of the base threshold and the threshold value for the pixel. If the sum of the pixel value and the error value is greater, then the pixel is supplied with the designated color 425a-d. Otherwise, the pixel is not supplied with the designated color.
The error diffusion blocks 405a-d then compute updated error values based on the above comparison for a scanline and store the updated error values in the error scanline buffer memory 415a-d corresponding to the same color. Likewise, the error diffusion blocks 405a-d compute updated threshold values based on the above comparison for a scanline and store the updated threshold values in the error scanline buffer memory 420a-d corresponding to the same color. Accordingly, slow-scan error and threshold information is passed from preceding scanlines to subsequent scanlines using this process.
FIG. 5 depicts a traditional threshold stamping distribution profile that is added to the threshold buffer memory after stamping a “black” (or “dark” pixel). The magnitude of the threshold adjustment is typically largest at the central point (TN) of pixel binarization and decays to zero several pixels away (for example, TN+12 and TN−12). As such, this has the desired effect of pushing subsequent printed dot(s) away from a printed dot while still maintaining the overall binary output level. The overall result of this processing shifts the dot placement of surrounding downstream pixels in the opposite direction of the “worm” response. As a result, a visually pleasing and uniform binary output is delivered. The distribution shown in FIG. 5 represents the effects of one stamped pixel. If multiple pixels are stamped, the threshold scanline buffer memory includes the sum of the threshold adjustments of each stamped pixel.
FIG. 6A depicts an error diffusion rendered binary image using threshold stamping. As stated above the rendered binary image is devoid of the “worm” artifacts present in FIG. 2. FIG. 6B depicts an error diffusion threshold delta image. The dark areas correspond to areas in which the threshold delta value is greater than zero for a highlight region. If the location is darker, then the threshold delta value is higher for that location. The slow-scan “decay” of the threshold delta is essential to rendering a pleasing binary output dot structure since it is desired that any threshold adjustment only affect the dot-placement of localized “neighboring” pixels while leaving other areas unaffected. The stamping applied in FIG. 6A directly correlates to the location and magnitude of the threshold stamping profile in FIG. 6B. For example, the arrows in FIGS. 6A and 6B indicate the correspondence between two such pixels/thresholds.
Although threshold stamping produces excellent image quality with pleasing dot structures, it requires numerous computations to achieve the desired output rendering effect. Accordingly, the overall throughput performance of the algorithm is limited and could not typically be used for high-speed image processing applications.
FIG. 7 depicts a single-port synchronous memory storing a scanline of threshold data performing a read-modify-write access. The single-port synchronous memory is a typical memory structure used in an ASIC to store a scanline of data for image processing context information. However, threshold stamping requires numerous computations per pixel in order to alter the threshold level(s) around the pixel being “stamped.” In a typical implementation, as many as 25 “read/modify/write” operations are performed in a single system clock cycle. In this case, any threshold adjustment is limited by the single-port memory architecture (i.e., one address and data bus). Accordingly, at least 2 memory clock cycles are required to perform a “read/modify/write” operation. Although dual- and triple-port memories are available that would reduce the access time by one-half and one-third, respectively, such memories are more complex and consume much more silicon real estate than single-port memories.
As shown in FIG. 7, one solution includes a phase-lock-loop (PLL) to increase the clock rate in order to successively/serially retrieve and modify the buffer's threshold data within one system clock cycle. However, this technique becomes impractical for any high-speed application since the RAM clock frequency would have to be increased by 50× over the system clock rate (25 operations×2 cycles/operation). For a 75 MHz system clock, the resulting memory clock frequency is 3.75 GHz. In other words, for a high-speed application, the memory clock speed would result in a prohibitively expensive memory solution.
What is needed is an error diffusion method and system that enables high-speed error diffusion while performing threshold stamping.
A need exists for an error diffusion method and system that reduces the worm effects traditionally caused in highlight and shadow regions of an image.
A further need exists for a method of reducing the memory size and number of memory accesses for an error diffusion algorithm while substantially maintaining image quality.
The present disclosure is directed to solving one or more of the above-listed problems.